import java.util.*;
//NC1 大数加法
public class Solution {
    /**
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        StringBuilder result = new StringBuilder();
        int carry = 0; // 进位
        int i = s.length() - 1;
        int j = t.length() - 1;

        // 从低位到高位逐位相加
        while (i >= 0 || j >= 0 || carry != 0) {
            int digit1 = i >= 0 ? s.charAt(i) - '0' : 0; // 获取 s 的当前位
            int digit2 = j >= 0 ? t.charAt(j) - '0' : 0; // 获取 t 的当前位

            int sum = digit1 + digit2 + carry; // 当前位的和
            carry = sum / 10; // 更新进位
            result.append(sum % 10); // 取个位数加入结果
            i--;
            j--;
        }

        // 翻转结果并返回
        return result.reverse().toString();
    }
}


//NC40 链表相加(二)
 class Solution1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */

    class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
          this.val = val;
        }
    }

    public ListNode addInList(ListNode head1, ListNode head2) {

        ListNode temp1=reverseList(head1);
        ListNode temp2=reverseList(head2);

        // 创建虚拟头节点
        ListNode newH = new ListNode(-1);
        ListNode tmp = newH;

        // 开始加法操作
        int carry = 0; // 记录进位
        while(temp1!=null||temp2!=null||carry!=0){
            int sum=carry;
            if(temp1!=null){
                sum+=temp1.val;
                temp1=temp1.next;
            }
            if(temp2!=null){
                sum+=temp2.val;
                temp2=temp2.next;
            }
            tmp.next=new ListNode(sum%10);
            tmp=tmp.next;
            carry=sum/10;
        }

        return  reverseList(newH.next);
    }
    public ListNode reverseList(ListNode headA) {
        ListNode cur = headA.next;
        headA.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=headA;
            headA=cur;
            cur=curNext;
        }
        return headA;
    }
}




//NC10 大数乘法
 class Solution2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        int n = s.length()+t.length();
        int[] arr = new int[n];

        for(int i=s.length()-1;i>=0;i--){
            for(int j=t.length()-1;j>=0;j--){
                int x=s.charAt(i)-'0';
                int y=t.charAt(j)-'0';
                int carry=x*y/10;
                int remainder=x*y%10;
                arr[i+j+1]+=remainder;
                if(arr[i+j+1]>=10){
                    carry+=arr[i+j+1]/10;
                    arr[i+j+1]%=10;
                }
                arr[i+j]+=carry;
            }
        }
        StringBuffer res = new StringBuffer();
        for(int i=0;i<arr.length;i++){
            if(arr[i]!=0||res.length()!=0){
                res.append(arr[i]);
            }
        }
        return res.length()==0?"0":res.toString();
    }
}
